package com.leetcode.weekly.contest.no281th;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

/**
 * @author 覃国强
 * @date 2022-02-20 11:04
 */
public class A03_构造限制重复的字符串 {


  static
  class Solution {
    public String repeatLimitedString(String s, int repeatLimit) {
      if (s == null || s.length() == 0) {
        return s;
      }

      char[] chars = s.toCharArray();
      Map<Character, Node> map = new TreeMap<>(Comparator.reverseOrder());
      for (char ch : chars) {
        if (!map.containsKey(ch)) {
          map.put(ch, new Node(ch));
        }
        ++map.get(ch).num;
      }
      List<Node> nodes = new ArrayList<>();
      for (Entry<Character, Node> entry : map.entrySet()) {
        nodes.add(entry.getValue());
      }
      if (nodes.size() == 1) {
        return new String(chars, 0, Math.min(repeatLimit, chars.length));
      }

      StringBuilder sb = new StringBuilder();
      int curIndex = 0;
      int nextIndex = 1;
      while (curIndex < nodes.size()) {
        Node node = nodes.get(curIndex);
        while (node.num > 0) {
          int time = Math.min(repeatLimit, node.num);
          for (int i = 0; i < time; ++i) {
            sb.append(node.ch);
          }
          node.num -= time;
          if (node.num > 0) {
            if (nextIndex >= nodes.size()) {
              return sb.toString();
            }
            Node nextNode = nodes.get(nextIndex);
            sb.append(nextNode.ch);
            nextNode.num--;
            if (nextNode.num == 0) {
              ++nextIndex;
            }
          }
        }
        curIndex = nextIndex;
        ++nextIndex;
      }

      return sb.toString();
    }


    class Node {
      char ch;
      int num;

      Node(char ch) {
        this.ch = ch;
      }
    }
  }

}
